# !/usr/bin/env python
# -*- coding: utf-8 -*-

# 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
#
# 算法的时间复杂度应该为 O(log (m+n)) 。
#
#  
#
# 示例 1：
#
# 输入：nums1 = [1,3], nums2 = [2]
# 输出：2.00000
# 解释：合并数组 = [1,2,3] ，中位数 2
# 示例 2：
#
# 输入：nums1 = [1,2], nums2 = [3,4]
# 输出：2.50000
# 解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
#  
#
#  
#
# 提示：
#
# nums1.length == m
# nums2.length == n
# 0 <= m <= 1000
# 0 <= n <= 1000
# 1 <= m + n <= 2000
# -106 <= nums1[i], nums2[i] <= 106
#
# 来源：力扣（LeetCode）
# 链接：https://leetcode.cn/problems/median-of-two-sorted-arrays
# 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
from typing import List


class Solution:
    # 有序数组合并 时间复杂度O(m + n)
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        m = len(nums1)
        n = len(nums2)
        i = 0
        j = 0
        nums = []
        while i < m and j < n:
            if nums1[i] < nums2[j]:
                nums.append(nums1[i])
                i += 1
            else:
                nums.append(nums2[j])
                j += 1
        while i < m:
            nums.append(nums1[i])
            i += 1
        while j < n:
            nums.append(nums2[j])
            j += 1
        length = len(nums)
        a = length // 2
        mod = length % 2
        if mod == 0:
            return (nums[a] + nums[a - 1]) / 2
        return nums[a]

    # 求合并序列的第k小的数 时间复杂度O(log(m + n))
    def findMedianSortedArrays2(self, nums1: List[int], nums2: List[int]) -> float:
        pass


if __name__ == '__main__':
    nums1 = []
    nums2 = [2, 3]
    s = Solution()
    print(s.findMedianSortedArrays(nums1, nums2))
